package 图;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
/**
 * 这道题 远比 你想的 复杂
 * 各种细节 方面 
 * 
 * 对比 我写的  这个 解法 和  Solution  类的  解法  的 区别 
 * 区别点 在于 判断  已经 锁死的 节点的 方法  他 好像 给 我 提供了 一些 思路 
 *   if(minChange[a[0]][a[1]]<a[2]){
            	continue;
            	}
      就这 三行代码 让我   思绪万千  也让我 明白 了 一些  东西
   		if(vis[cur[0]][cur[1]])
				continue;
	     vis[cur[0]][cur[1]] = true;
 */



/**
 * 我好像明白  了 这道题 为啥  不用 建图 了
 * 
 * 建图 的 目的 是为了  对 图中的 节点集合 与  边 集合 能够有 整体 的掌控 
 * 但是 这道题 如果  看成 是 一张图 的 话 还是 有点 特殊性 
 * ① ： 二维 点的  表示 （x，y） 表示 一个点 
 * 当前 cur 节点 （x，y） 那么 其 邻接点 就比较 有意思
 * （x+(-)1 , y + (-) 1） 就是 其 邻接点 
 * 正是因为这种特殊性 才并没有 建图 而是  直接 进行 最短路 就算 (dijkstra)
 * 当初 就是 卡在  下面 这个二维 数组    (完全不懂 这个 二维数组的 意思 )   以及 下面那个 一维数组 的 意思 
 * int [][] dir ={{0,1},{0,-1},{1,0},{-1,0}}; 
 * int towards []={'>','<','v','^'};
 * 但是 在 进行 了 思考 和 无限的  折磨 之后 发现  理解起来 还是 很 清晰的
 * @author I adore you
 *
 */
public class LCP56信物传送 {
	public static void main(String [] args) {
		String  matrix[]  = {">>v","v^<","<><"};
		int start [] = {0,1};
		int end [] = {2,0};
		Solution s = new Solution();
		int ans = s.conveyorBelt(matrix, start, end);
		System.out.println(ans);
		System.out.println(solution(matrix,start,end));
	}
	/**
	 * 返回 最小 change 数
	 * x  是 行 i
	 * y 是 列    j
	 * 在这个   图上 跑一遍 最短路 就可以 了 
	 * 但是 这个 题的 最短 路  指的的 这个时候 不是  距离 了 而是  最小 change 数
	 */
	public static int solution(String martix[],int []start,int end[]) {
		int dir [][] = {{0,1},{0,-1},{-1,0},{1,0}};
		char towards [] = {'>','<','^','v'};
		int row = martix.length;
		int col = martix[0].length();
		char [][] cMartix= new char [row][col];
		for(int i = 0;i < row ;i++) {
			cMartix[i] = martix[i].toCharArray();
		}
		// 这就是 最短路的 dis 数组 
		int [][] minChange = new  int[row][col];
		int max = Integer.MAX_VALUE;
		// 将 minChange 数组中的 值 初始化 为 一个 很大的值 infinite 
		for(int arr [] : minChange) {
			Arrays.fill(arr, max);
		}
		/**
		 * 那这里的    vis 数组 也  得 整成二维  了 
		 * 一个 (x,y) 坐标 表示 一个 点  时刻 记住 这个 核心 点 就行了
		 * 这个  优先队列得 泛型 是一个 int [] arr 长度 为 3 
		 * arr[0] 横坐标 arr[1]   纵坐标  arr[2]  表示的  就是  最短 距离 (最小change)
		 * 时刻想着  只不过 是  一个 graph 中  节点 不是 用 编号 而是  用 坐标 ( x,y )  表示 了而已
		 */
		boolean vis [][] = new boolean [row][col];
		minChange[start[0]][start[1]] = 0;
		PriorityQueue<int []>  queue = new PriorityQueue<>((o1,o2) -> (o1[2] - o2[2]));  
		queue.add(new int []{start[0],start[1],0});
		while(!queue.isEmpty()) {
			int  [] cur = queue.poll();
//		     if(minChange[cur[0]][cur[1]]<cur[2]){
//	            	continue;
//	            	}
//			 已经 锁死的点 就不再 走了 
			if(vis[cur[0]][cur[1]])
				continue;
			/**
			 *   这里  不一样的  点  就 发生了  巨大的  改变
			 * 按照 正常的 图 的 遍历来说  下面 应该是 遍历其 邻接点 的时候了
			 * 这里的 代码 也是 去 遍历 并更新 其 邻接点的 minChange(最短路) 
			 * 但是 这个 图 有一定的 特殊性 就是  其 邻接点  与 cur 节点的  之间的 表示关系 就很特殊
			 * 这里 一定要多理解一下这里的代码    
			 */
			for(int i = 0;i < 4 ;i++) {
				int x = cur[0] + dir[i][0];
				int y = cur[1] + dir[i][1];
//				int change = cur[2];
				if(x>= 0 && x < row && y >= 0 && y < col) {
					int change = cur[2];
					if(cMartix[cur[0]][cur[1]] != towards[i]) {
						change++;
					}
					if(minChange[x][y] > change) {
						minChange[x][y] = change;
						queue.add(new int [] {x,y,minChange[x][y]});
					}
						
				}
			}
			// 将当前节点 锁死 
			vis[cur[0]][cur[1]]  = true;
		}
		return minChange[end[0]][end[1]];
	}

}
class Solution {
    int shift[][]={{0,1},{0,-1},{1,0},{-1,0}};
    char move[]={'>','<','v','^'};
    public int conveyorBelt(String[] matrix, int[] start, int[] end) {
        char c[][]=new char[matrix.length][];
        for(int i=0;i<c.length;i++){
        	c[i]=matrix[i].toCharArray();
        	}
        int minChange[][]=new int[c.length][c[0].length];
        for(int i=0;i<c.length;i++){
        	Arrays.fill(minChange[i],10005);
        	}
        Queue<int[]> q=new PriorityQueue<>((a,b)->a[2]-b[2]);
        minChange[start[0]][start[1]]=0;
        q.add(new int[]{start[0],start[1],0});
        while(q.size() > 0){
            int a[]=q.poll();
            if(minChange[a[0]][a[1]]<a[2]){
            	continue;
            	}
            for(int i=0;i<4;i++){
                int x=a[0]+shift[i][0],y=a[1]+shift[i][1];
                if(x>=0&&x<c.length&&y>=0&&y<c[0].length){
                    int change=a[2];
                    if(c[a[0]][a[1]]!=move[i]){
                    	change++;
                    	}
                    if(minChange[x][y]>change){
                        minChange[x][y]=change;
                        q.add(new int[]{x,y,change});
                    }
                }
            }
        }
        return minChange[end[0]][end[1]];
    }
}